package com.liunian.test;

import java.util.Arrays;

public class LargestSumAfterKNegations {

	public int largestSumAfterKNegations(int[] nums, int k) {
		int sum = 0;
		Arrays.sort(nums);
		for (int i = 0; i < nums.length; i++) {
			if (k > 0 && nums[i] < 0) {
				nums[i] = -nums[i];
				k--;
			}
			sum += nums[i];
		}
		Arrays.sort(nums);
		return sum - (k % 2 == 0 ? 0 : 2 * nums[0]);
	}

}
